#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <vector>

#define EPS 0.0001
#define dist(x1, x2, y1, y2) sqrt((x1-y1)*(x1-y1) + (x2-y2)*(x2-y2))

using namespace std;

double isLeft(double x0, double y0, double x1, double y1, double x2, double y2) {
 return (x1-x0)*(y2-y0)-(x2-x0)*(y1-y0);
}


// Point in Polygon (x[], y[]) (note wn = 0 iff P is outside)

int PnPoly(double px, double py, vector<double> x, vector<double> y)
{
 x.push_back(x[0]);
 y.push_back(y[0]);
 int wn = 0;
 for(int i = 0; i < x.size()-1; i++)
  if(y[i] <= py && y[i+1] > py && isLeft(x[i],y[i],x[i+1],y[i+1],px,py)>0) wn++;
 else if(y[i] > py && y[i+1] <= py && isLeft(x[i],y[i],x[i+1],y[i+1],px,py)<0) wn--;
 return wn;
}

//dist from (px,py) to line (ax,ay)-(bx,by). Coords of closest point stored in //(cpx,cpy)

double distToLine(double ax,double ay, double bx,double by, double px, double py, double *cpx, double *cpy) {
double proj = ((px-ax)*(bx-ax)+(py-ay)*(by-ay))/((bx-ax)*(bx-ax)+(by-ay)*(by-ay));
*cpx = ax+proj*(bx-ax);  *cpy = ay+proj*(by-ay);
return sqrt((px-*cpx)*(px-*cpx) + (py-*cpy)*(py-*cpy));
}

double distToLineSeg(double ax,double ay, double bx, double by, double px, double py, double *cpx, double *cpy) {
if((bx-ax)*(px-ax)+(by-ay)*(py-ay) < EPS)
{
 *cpx = ax; *cpy = ay;
 return dist(ax,ay,px,py);
}
if((ax-bx)*(px-bx)+(ay-by)*(py-by) < EPS)
{
 *cpx = bx; *cpy = by;
 return dist(bx,by,px,py);
}
return distToLine(ax,ay,bx,by,px,py,cpx,cpy);
}


//line intersection of (x[0],y[0])-(x[1],y[1]) and (x[2],y[2])-(x[3],y[3]). //Intersection point stored in r[]

bool lineIntersect(double x[], double y[], double r[])
{
double n[2]; n[0] = y[3]-y[2]; n[1] = x[2]-x[3];
double denom = n[0]*(x[1]-x[0]) + n[1]*(y[1]-y[0]);
if(fabs(denom) < EPS) return 0;
double num = n[0]*(x[0]-x[2]) + n[1]*(y[0]-y[2]);
double t = -num/denom;
r[0] = x[0]+t*(x[1]-x[0]); r[1] = y[0]+t*(y[1]-y[0]);
return 1;
}


//Do segments (x[0],y[0])-(x[1],y[1]) and (x[2],y[2])-(x[3],y[3]) intersect?

bool lineSegIntersect(vector<int>& x, vector<int>& y)
{
long long t1 = (y[3]-y[0])*(x[1]-x[0]) - (x[3]-x[0])*(y[1]-y[0]);
long long t2 = (y[2]-y[0])*(x[1]-x[0]) - (x[2]-x[0])*(y[1]-y[0]);
long long t3 = (y[1]-y[2])*(x[3]-x[2]) - (x[1]-x[2])*(y[3]-y[2]);
long long t4 = (y[0]-y[2])*(x[3]-x[2]) - (x[0]-x[2])*(y[3]-y[2]);

if(t1*t2 > 0 || t3*t4 > 0) return 0;
if(t1 != 0 || t2 != 0 || t3 != 0 || t4 != 0) return 1;
return (max(y[1],y[0]) >= min(y[3],y[2])) && (max(x[1],x[0]) >= min(x[3],x[2]) && max(y[3],y[2]) >= min(y[1],y[0]) && max(x[3],x[2]) >= min(x[1],x[0]) ); }

//circle through (x[0],y[0]), (x[1],y[1]), (x[2],y[2]). Centre returned in // (r[0],r[1]). If points are collinear, returns -1.

double circ3pts(double x[], double y[], double r[])
{
double lix[4],liy[4];
lix[0] = 0.5*(x[0]+x[1]); liy[0] = 0.5*(y[0]+y[1]);
lix[1] =lix[0]+y[1]-y[0]; liy[1] = liy[0]+x[0]-x[1];
lix[2] = 0.5*(x[1]+x[2]); liy[2] = 0.5*(y[1]+y[2]);
lix[3] = lix[2]+y[2]-y[1]; liy[3]=liy[2]+x[1]-x[2];
if(!lineIntersect(lix,liy,r) ) return -1;
return sqrt((r[0]-x[0])*(r[0]-x[0]) + (r[1]-y[0])*(r[1]-y[0]));
}

//is P inside a collinear segment S0-S1?
int inSegment(double px, double py, double S0x, double S0y, double S1x, double S1y) {
if(S0x != S1x)
{
 if((S0x <= px && px <= S1x) || (S0x >= px && px >= S1x)) return 1;
}
else
{  if((S0y <= py && py <= S1y) || (S0y >= py && py >= S1y)) return 1;
}
return 0;
}

//Intersection of line segments S10-S11, S20-S21. Output is *IO = intersect // point (when it exists), *I1 = endpoint of intersect segment [I0,I1] (when it // exists). Return 0 = disjoint, 1 = intersect in unique I0, 2 = overlap in //[I0,I1].

double I0x,I0y,I1x,I1y;
int intSegments(double S10x,double S10y, double S11x, double S11y, double S20x, double S20y, double S21x, double S21y) {
 double ux = S11x-S10x; double uy = S11y - S10y;
 double vx = S21x-S20x; double vy = S21y - S20y;
 double wx = S10x-S20x; double wy = S10y - S20y;
 double D = ux*vy-uy*vx;

 if(fabs(D) < EPS)
 {
  if(ux*wy-uy*wx != 0 || vx*wy-vy*wx != 0) return 0;
  double du = ux*ux + uy*uy; double dv = vx*vx + vy*vy;
  if(du == 0 && dv == 0)
  {
   if(S10x != S20x || S10y != S20y) return 0;
   I0x = S10x; I0y = S10y;
   return 1;
  }
  if(du == 0)
  {
   if(inSegment(S10x,S10y,S20x,S20y,S21x,S21y)==0) return 0;
   I0x = S10x; I0y = S10y; return 1;
  }
  if(dv == 0)
  {
   if(inSegment(S20x,S20y,S10x,S10y,S11x,S11y)==0) return 0;
   I0x = S20x; I0y = S20y; return 1;
  }
  double t0,t1;
  double w2x = S11x-S20x; double w2y = S11y-S20y;
  if(vx != 0) {t0 = wx/vx; t1 = w2x/vx;}
  else {t0 = wy/vy; t1 = w2y/vy;}
  if(t0>t1) swap(t0,t1);
  if(t0>1 || t1 < 0) return 0;
  if(t0 < 0) t0 = 0;
  if(t1 > 1) t1 = 1;
  if(t0 == t1)
  {
    I0x = S20x + t0*vx; I0y = S20y + t0*vy; return 1;
  }
  I0x = S20x + t0*vx; I0y = S20y + t0*vy;
  I1x = S20x + t1*vx; I1y = S20y + t1*vy;
  return 2;
 }
 double sI = (vx*wy-vy*wx)/D;
 if(sI < 0 || sI > 1) return 0;
 double tI = (ux*wy-uy*wx)/D;
 if(tI < 0 || tI > 1) return 0;
 I0x = S10x + sI*ux; I0y = S10y + sI*uy;
 return 1;
}


// Tangency points from point A to circle of radius r centred at C

/*
Let d = dist(a,c)
If (d < r) then a is in the circle
If (d == r) then a is on the circle
Else
 double sina = r/d, d1 = r*sina, vx = a.x-c.x, vy = a.y-c.y, vlen = len(vx,vy);
 vx /= vlen, vy /= vlen;
 double x0 = c.x + vx*d1, y0 = c.y + vy*d1, nx = -vy, ny = vx;
 double n = sqrt(r*r-d1*d1);
 Point p1 = new Point(x0 + n*nx, y0+n*ny);
 Point p2 = new Point(x0 - n*nx, y0 - n*ny);
 */

//p1 and p2 are the points of tangency
